package com.cwj.lab4.查找.散列表;

import com.cwj.lab1.myArrayList;
import com.cwj.lab4.Tool;

import java.util.Objects;
/**
 * 哈希表
 * 线性扫描法冲突处理实现
 * */
public class Hash_table_2<E, T> implements Hash<E, T> {
    //节点
    static class Node<E, T> {
        E key;//键
        T data;//数据域
        Integer codeHash;//key对应的哈希值，避免扩容时存放计算哈希值

        public Node(E key, T data, Integer code) {
            this.key = key;
            this.data = data;
            this.codeHash = code;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node<?, ?> node = (Node<?, ?>) o;
            if (node.codeHash != null && this.codeHash != null) {
                return this.codeHash.equals(node.codeHash);
            }
            return key.equals(node.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }
    }
//存放节点
    private myArrayList<Node<E, T>> hashList;
    //元素数目
    private int len;
    //有效表长（一定为质数）
    private int P;

    public Hash_table_2() {
        this(14);
    }

    public Hash_table_2(int size) {
        this.P = Tool.caluP(size);
        this.len = 0;
        this.hashList = this.preSize(size);
    }

    private myArrayList<Node<E, T>> preSize(int size) {
        myArrayList<Node<E, T>> list = new myArrayList<>();
        for (int i = 0; i < size; i += 1) {
            list.addLast(null);
        }
        return list;
    }
/**
 * 查找
 * @param key 键
 * @return 对应的值
 * */
    public T find(E key) {
        int codeHash = key.hashCode();
        int code = codeHash % this.P;
        for (int i = 0; i < this.hashList.size(); i++) {
            Node<E, T> nn = this.hashList.get(code + i);
            if (nn != null && nn.codeHash == codeHash) {
                return nn.data;
            } else if (nn == null) {
                return null;
            }
        }
        return null;
    }
/**
 * 修改或设置
 * @param key 键
 * @param data 对应的值
 * */
    public boolean set(E key, T data) {
        this.len += 1;
        resize();
        return this.set(this.hashList, key, data, null);
    }

    private boolean set(myArrayList<Node<E, T>> list, E key, T data, Integer codeHash) {
        this.checkSIZE(list);
        if (codeHash == null) {
            codeHash = key.hashCode();
        }
        int code = codeHash % this.P;
        for (int i = 0; i < this.hashList.size(); i++) {
            Node<E, T> nn = list.get(code + i);
            if (nn == null) {
                list.set(code + i, new Node<>(key, data, codeHash));
                return true;
            } else if (nn.codeHash.equals(codeHash)) {
                list.get(code + i).data = data;
                return false;
            }
        }
        return false;
    }
//扩容，改变容量
    private void resize() {
        int size = this.hashList.size();
        if (len > size * 0.75) {
            resize((int) (size * 1.75));
        }
    }

    private void resize(int size) {
        myArrayList<Node<E, T>> oldList = this.hashList;
        this.hashList = preSize(size);
        System.out.println("resize.size=" + this.hashList.size() + "\tlen=" + this.len);
        for (int i = 0; i < oldList.size(); i++) {
            Node<E, T> nn = oldList.get(i);
            //重新插入数据
            if (nn != null)
                set(this.hashList, nn.key, nn.data, nn.codeHash);
        }
    }
//检查函数
    private void checkSIZE(myArrayList<Node<E, T>> list) {
        int size = list.size();
        if (len > size * 0.75) {
            throw new RuntimeException("有参set函数能够被使用的前提是len<size*0.75");
        }
    }
//计算小于表长的最大质数
    @Override
    public int getP() {
        return this.P;
    }
}
